package j2025.j03;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author 猫大仙
 */
public class j0310 {
    /**
     * 原地哈希
     * @param nums
     * @return
     * 时O(N),空O(1)
     */
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while(nums[i]>0 && nums[i]<=n && nums[nums[i]-1]!=nums[i]){
                swap(nums,i,nums[i]-1);
            }
        }
        for (int i = 0; i < n; i++) {
            if(nums[i]!=i+1){
                return i+1;
            }
        }
        return n+1;
    }
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void setZeroes(int[][] matrix) {
        int m = matrix.length,n = matrix[0].length;
        //记录第一列是否原本存在0
        boolean firstCol = false;
        for (int i = 0; i < m; i++) {
            if(matrix[i][0] == 0){
                firstCol = true;
            }
            for (int j = 1; j < n; j++) {
                if(matrix[i][j] == 0){
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        for (int i = m-1; i >= 0; i--) {
            for (int j = 1; j < n; j++) {
                if(matrix[i][0] == 0 || matrix[0][j] == 0){
                    matrix[i][j] = 0;
                }
            }
            if(firstCol){
                matrix[i][0] = 0;
            }
        }
    }

    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length,n = matrix[0].length;
        int left = 0,right = n-1,top = 0,bottom = m-1;
        List<Integer> ret = new ArrayList<>();
        while(true){
            for (int i = left; i <= right; i++) {
                ret.add(matrix[top][i]);
            }
            if(++top>bottom)  break;
            for (int i = top; i <= bottom; i++) {
                ret.add(matrix[i][right]);
            }
            if(--right<left) break;
            for (int i = right; i >= left; i--) {
                ret.add(matrix[bottom][i]);
            }
            if(--bottom<top) break;
            for (int i = bottom; i >= top; i--) {
                ret.add(matrix[i][left]);
            }
            if(++left>right) break;
        }
        return ret;
    }

    public void rotate(int[][] matrix) {
        int m = matrix.length,n = matrix[0].length;
        /**
         * m[i][j]
         * m[j][n-i-1]
         * m[n-i-1][n-j-1]
         * m[n-j-1][i]
         */
        for (int i = 0; i < n/2; i++) {
            for (int j = 0; j < (n+1)/2; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[n-j-1][i];
                matrix[n-j-1][i] = matrix[n-i-1][n-j-1];
                matrix[n-i-1][n-j-1] = matrix[j][n-i-1];
                matrix[j][n-i-1] = tmp;
            }
        }
    }
}
